/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
export var duplicateZeros = function (arr) {
  const queue = []
  for (let i = 0; i < arr.length; i++) {
    const n = arr[i]
    if (queue.length === 0 && n !== 0) continue
    if (queue.length > 0) {
      arr[i] = queue.shift()
      if (n === 0) queue.push(0)
    }
    queue.push(n)
  }
}

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
export var duplicateZeros2 = function (arr) {
  const stack = []
  for (let i = 0; i < arr.length; i++) {
    const n = arr[i]
    if (n === 0) stack.push(0)
    stack.push(n)
    if (stack.length === arr.length) break
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    arr[i] = stack.pop()
  }
}

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
export var duplicateZeros3 = function (arr) {
  for (let i = 0; i < arr.length; i++) {
    const n = arr[i]
    if (n === 0) {
      arr.splice(i + 1, 0, 0)
      arr.pop()
      i++
    }
  }
}
